package com.data_structure_algorithm.algorithm;

/**
 * @Authror PABLO
 * @Date 2022/4/5 16:43
 * @Desc  1-7数列内，起始点S到目标点K在N步数内的多少种走法
 */
public class Gap {
    public static void main(String[] args) {

        //1-7之间
        int start = 2;//起始点
        int end = 4;//目标点
        int gap = 4;//步数
        int local = 7;//一共有多少个位置

        int walk = walk(local, start, end, gap);
        System.out.println(walk);
    }

    /**
     * @Description:
     * @Author: PABLO
     * @Date: 2022/4/5 16:47
     * @Params: [local 多少个位置,
     * start 起始位置 ,
     * end 目标点 ,
     * gap 步数]
     * @Return: int 返回符合条件的数量
     **/
    private static int walk(int local, int start, int end, int gap) {
        //建立缓存，本次递归调用，start 和 gap是不断变化且配合使用的,缓存每次递归返回的结果
        //start的范围1-7
        //gap 范围 0- 4
        int[][] cache = new int[local + 1][gap + 1];
        //默认均为-1
        for (int i = 0; i <= local; i++) {
            for (int j = 0; j <= gap; j++) {
                cache[i][j] = -1;
            }
        }

        return process(start, gap, end, local, cache);
    }

    /**
     * @Description:返回可达到要求的数量 计数
     * @Author: PABLO
     * @Date: 2022/4/5 16:50
     * @Params: [cur 当前位置, gap 还剩步数, end 终点位置, local 一共有多少个位置]
     * @Return: int
     **/
    private static int process(int cur, int gap, int end, int local, int[][] cache) {
        //该方式之前走过
        if (cache[cur][gap] != -1) {
            return cache[cur][gap];
        }
        int result = 0;

        //如果当前停下了并且在目标点位置，说明找到了
        if (gap == 0) {
            result = cur == end ? 1 : 0;
            //步数没走完，如果当前没找到，判断边界
        } else if (cur == 1) { //1的位置，下一步必须走到2
            result = process(cur + 1, gap - 1, end, local, cache);

        } else if (cur == local) { //7的位置，下一步必须走到6  边界
            result = process(cur - 1, gap - 1, end, local, cache);

        } else {
            //可左可右
            result = process(cur - 1, gap - 1, end, local, cache) +
                    process(cur + 1, gap - 1, end, local, cache);
        }

        //将结果放入cache
        cache[cur][gap] = result;

        return result;
    }
}
